Optimizing debt collections using constrained reinforcement learning.

Grouped graphical Granger modeling methods for temporal causal modeling.

Spatial%2Dtemporal causal modeling for climate change attribution.
Attribution of climate change to causal factors has been based predominantly on simulations using physical climate models, which have inherent limitations in describing such a complex and chaotic system. We propose an alternative, data centric, approach that relies on actual measurements of climate observations and human and natural forcing factors. Specifically, we develop a novel method to infer causality from spatial-temporal data, as well as a procedure to incorporate extreme value modeling into our method in order to address the attribution of extreme climate events, such as heatwaves. Our experimental results on a real world dataset indicate that changes in temperature are not solely accounted for by solar radiance, but attributed more significantly to CO2 and other greenhouse gases. Combined with extreme value modeling, we also show that there has been a significant increase in the intensity of extreme temperatures, and that such changes in extreme temperature are also attributable to greenhouse gases. These preliminary results suggest that our approach can offer a useful alternative to the simulation-based approach to climate modeling and attribution, and provide valuable insights from a fresh perspective.
Proximity%2DBased Anomaly Detection Using Sparse Structure Learning.

Grouped graphical Granger modeling for gene expression regulatory networks discovery.

Multi%2Dclass cost%2Dsensitive boosting with p%2Dnorm loss functions.

Temporal causal modeling with graphical granger methods.
The need for mining causality, beyond mere statistical correlations, for real world problems has been recognized widely. Many of these applications naturally involve temporal data, which raises the challenge of how best to leverage the temporal information for causal modeling. Recently graphical modeling with the concept of “Granger causality”, based on the intuition that a cause helps predict its effects in the future, has gained attention in many domains involving time series data analysis. With the surge of interest in model selection methodologies for regression, such as the Lasso, as practical alternatives to solving structural learning of graphical models, the question arises whether and how to combine these two notions into a practically viable approach for temporal causal modeling. In this paper, we examine a host of related
Active ensemble learning Application to data mining and bioinformatics.

Using secure coprocessors for privacy preserving collaborative data mining and analysis.
secure coprocessors for privacy preserving
A Parameterized Probabilistic Model of Network Evolution for Supervised Link Prediction.

Outlier detection by active learning.

Business Performance Management System for CRM and Sales Execution.

Improvements to the Linear Programming Based Scheduling of Web Advertisements.

An iterative method for multi%2Dclass cost%2Dsensitive learning.
Cost-sensitive learning addresses the issue of classification in the presence of varying costs associated with different types of misclassification. In this paper, we present a method for solving multi-class cost-sensitive learning problems using any binary classification algorithm. This algorithm is derived using three key ideas: 1) iterative weighting; 2) expanding data space; and 3) gradient boosting with stochastic ensembles. We establish some theoretical guarantees concerning the performance of this method. In particular, we show that a certain variant possesses the boosting property, given a form of weak learning assumption on the component binary classifier. We also empirically evaluate the performance of the proposed method using benchmark data sets and verify that our method generally achieves better results than representative methods for cost-sensitive learning, in terms of predictive performance (cost minimization) and, in many cases, computational efficiency.
Cross channel optimized marketing by reinforcement learning.

Cross channel optimized marketing by reinforcement learning.

Cost%2DSensitive Learning by Cost%2DProportionate Example Weighting.
We propose and evaluate a family of methods for converting classifier learning algorithms and classification theory into cost-sensitive algorithms and theory. The proposed conversion is based on cost-proportionate weighting of the training examples, which can be realized either by feeding the weights to the classification algorithm (as often done in boosting), or by careful subsampling. We give some theoretical performance guarantees on the proposed methods, as well as empirical evidence that they are practical alternatives to existing approaches. In particular, we propose  costing, a method based on cost-proportionate rejection sampling and ensemble aggregation, which achieves excellent predictive performance on two publicly available datasets, while drastically reducing the computation required by other methods.
Reinforcement Learning with Immediate Rewards and Linear Hypotheses.
Abstract. We consider the design and analysis of algorithms that learn from the consequences of their actions with the goal of maximizing their cumulative reward, when • the consequence of a given action is felt immediately, and • a linear function, which is unknown a priori, (approximately) relates a feature vector for each action/state pair to the (expected) associated reward. We focus on two cases, one in which a continuous-valued reward is (approximately) given by applying the unknown linear function, and another in which the probability of receiving the larger of binary-valued rewards is obtained. For these cases we provide bounds on the per-trial regret for our algorithms that go to zero as the number of trials approaches infinity. We also provide lower bounds that show that the rate of convergence is nearly optimal.
Empirical Comparison of Various Reinforcement Learning Strategies for Sequential Targeted Marketing.
We empirically evaluate the performance of various reinforcement learning methods in applications to sequential targeted marketing. In particular, we propose and evaluate a progression of reinforcement learning methods, ranging from the &#034;direct&#034; or &#034;batch&#034; methods to &#034;indirect&#034; or &#034;simulation based&#034; methods, and those that we call &#034;semidirect &#034; methods that fall between them. We conduct a number of controlled experiments to evaluate the performance of these competing methods. Our results indicate that while the indirect methods can perform better in a situation in which nearly perfect modeling is possible, under the more realistic situations in which the system&#039;s modeling parameters have restricted attention, the indirect methods&#039; performance tend to degrade. We also show that semi-direct methods are effective in reducing the amount of computation necessary to attain a given level of performance, and often result in more profitable policies.
Sequential cost%2Dsensitive decision making with reinforcement learning.
Recently, there has been increasing interest in the issues of cost-sensitive learning and decision making in a variety of applications of data mining. A number of approaches have been developed that are effective at optimizing cost-sensitive decisions when each decision is considered in isolation. However, the issue of sequential decision making, with the goal of maximizing total benefits accrued over a period of time instead of immediate benefits, has rarely been addressed. In the present paper, we propose a novel approach to sequential decision making based on the reinforcement learning framework. Our approach attempts to learn decision rules that optimize a sequence of cost-sensitive decisions so as to maximize the total benefits accrued over time. We use the domain of targeted marketing as a testbed for empirical evaluation of the proposed method. We conducted experiments using approximately two years of monthly promotion data derived from the well-known KDD Cup 1998 donation data set. The experimental results show that the proposed method for optimizing total accrued benefits outperforms the usual targeted-marketing methodology of optimizing each promotion in isolation. We also analyze the behavior of the targeting rules that were obtained and discuss their appropriateness to the application domain.
Efficient Data Mining by Active Learning.

Online Learning of Binary and n%2Dary Relations over Clustered Domains.

Algorithmic Learning Theory
We shall present the construction and analysis of a universal estimator for the mathematical problem of supervised learning. In this problem, we observe the data z = (z1,..., zm)  ⊂ X × Y of m independent random observations zi = (xi, yi), i = 1,..., m, identically distributed according to a probability ρ on a product space X × Y. We are interested in estimating the regression function fρ(x) defined as the conditional expectation of the random variable y at x: fρ(x): = ydρ(y|x) Y with ρ(y|x) the conditional probability measure with respect to x. The estimator fz is assessed by the measure of the error ‖fρ − fz ‖ in the L 2 (X, ρX) metric with ρX the marginal probability which is unknown. This type of problem is refered to as distribution-free, see [?] for a general introduction. Universal means that the estimator does not depend on any a priori assumptions about the regression function to be estimated. Our universal estimator, introduced in [?], consists of a least-square fitting procedure using piecewise constant
Editors%27 Introduction.
This paper reports on solving instances with more than 10,000 data items in a few hours. Keane, Page, Naughton, Travers and McInerney report on a fully cross platform coarse-grained distributed application for building large phylogenetic trees. Their new system overcomes many of the limitations imposed by the current set of parallel phylogenetic programs and it is now publicly available. The next two papers deal with gene and protein sequence comparison. Alves, Caceres and Song present a new coarse-grained parallel algorithm for the all-substrings longest common subsequence operation which is used, e.g. to find approximate tandem repeats and the alignment of one sequence with several others that have a common subsequence. Driga, Lu, Schaeffer, Szafron, Charter and Parsons discuss parallel and sequential sequence alignment via a method called FastLSA. Experiments indicate that their method scales well and can be parameterized to take advantage of cache memory and main memory sizes
Efficient Mining from Large Databases by Query Learning.

Automatic recording agent for digital video server.

Efficient Mining from Large Databases by Query Learning.




The Lob%2DPass Problem.
We treat an on-line learning model named lob-pass problem, that is an extension of the bandit problem. The nonparametric case is considered, and a class of strategies which can obtain O(t  ffl  ) cumulative regret for arbitrary ffl ? 0 is constructed. It is also shown that no strategy can achieve O(log t).  I. Introduction  It is desirable to choose the best decision or reaction in the stochastic environment on which our knowledge is limited. In order to obtain the maximal cumulative gain, we need to compromise the exploration and exploitation processes. The bandit problem is a model of such a case [3][4][5][9]. In the real world, our actions may change the state of the environment. The lob-pass problem formulated by Abe and Takeuchi [1] is a simple example of such a case. They considered a model of tennis play in which a player has two alternatives &#034;lob&#034; and &#034;pass&#034;. The opponent is not in a fixed state but his state changes depending on the player&#039;s action. Let s be the rate of lobs i...


Associative Reinforcement Learning using Linear Probabilistic Concepts.
We consider the problem of maximizing the total number of successes while learning about a probability function determining the likelihood of a success. In particular, we consider the case in which the probability function is represented by a linear function of the attribute vector associated with each action/choice. In the scenario we consider, learning proceeds in trials and in each trial, the algorithm is given a number of alternatives to choose from, each having an attribute vector associated with it, and for the alternative it selects it gets either a success or a failure with probability determined by applying a fixed but unknown linear success probability function to the attribute vector. Our algorithms consist of a learning method like the Widrow-Hoff rule and a probabilistic selection strategy which work together to resolve the so-called exploration-exploitation tradeoff. We analyze the performance of these methods by proving bounds on the worst-case  regret, or how many less ...

Unintrusive Customization Techniques for Web Advertising.
Most online advertisement systems in place today use the concept of consumer targeting: Each user is identified and, according to his or her system setup, browsing habits and available off-line information, categorized in order to customize the advertisements for highest user responsiveness. This constant monitoring of a user&#039;s online habits, together with the trend to centralize this data and link it with other databases, continuously nurtures fears about the growing lack of privacy in a networked society. In this paper, we propose a novel technique of adapting online advertisement to a user&#039;s short term interests in a non-intrusive way. As a proof-of-concept we implemented a dynamic advertisement selection system able to deliver customized advertisements to users of an online search service or Web directory. No user-specific data elements are collected or stored at any time. Initial experiments indicate that the system is able to improve the average click-through rate substantially c...
Word Clustering and Disambiguation Based on Co%2Doccurence Data.

Empirical Comparison of Competing Query Learning Methods.

Query Learning Strategies Using Boosting and Bagging.

Collaborative Filtering Using Weighted Majority Prediction Algorithms.

Efficient Distribution%2DFree Population Learning of Simple Concepts.

Word Clustering and Disambiguation Based on Co%2Doccurrence Data
We address the problem of clustering words (or con-structing a thesaurus) based on co-occurrence data, and using the acquired word classes to improve the accuracy of syntactic disambiguation. We view this problem as that of estimating a joint probability dis-tribution specifying the joint probabilities of word pairs, such as noun verb pairs. We propose an effi-cient algorithm based on the Minimum Description Length (MDL) principle for estimating such a prob-ability distribution. Our method is a natural ex-tension of those proposed in (Brown et al., 1992) and (Li and Abe, 1996), and overcomes their draw-backs while retaining their advantages. We then coinbined this clustering method with the disam-I)iguation method of (Li and Abe, 1995) to derive a disambiguation method that makes use of both auto-matically constructed thesauruses and a hand-made thesaurus. The overall disambiguation accuracy achieved by our method is 85.2%, which compares favorably against the accuracy (82.4%) obtained by the state-of-the-art disambiguation method of (Brill and Resnik, 1994). 1
Generalizing Case Frames Using a Thesaurus and the MDL Principle.
this paper, we confine ourselves to the former issue, and refer the interested reader to Li and Abe (1996), which deals with the latter issue
Predicting Protein Secondary Structure Using Stochastic Tree Grammars.

Towards Realistic Theories of Learning.

Learning Dependencies between Case Frame Slots.
We address the problem of automatically acquiring case frame patterns (selectional patterns) from large corpus data. In particular, we propose a method of learning dependencies between case frame slots. We view the problem of learning case frame patterns as that of learning a multi-dimensional discrete joint distribution, where random variables represent case slots. We then formalize the dependencies between case slots as the probabilistic dependencies between these random variables. Since the nnmber of parameters in a multidimensional joint distribution is exponential in general, it is infiasible to accurately estimate them in practice. To overcome this difficulty, we settle with approximatiug the target joint distribution by the product of low order component distributions, based on corpus data. In particular we propose to employ an efficient learning algorithm based on the MDL principle to realize this task. Our experimental results indicate that for certain classes of verbs, the accuracy achieved in a disambiguation experiment is improved by using the acquired knowledge of dependencies.
Clustering Words with the MDL Principle.
We address the problcin of automatically  constructing a thesaurus by clustertug  words based on corpus data. We view  this problem as that of estimating a joint  distribution over the Cartesian product  of a partition of a set, of nouns and a  partition of a set of verbs, and propose  a learuing algorithm based on the Minimum  Description Leugth (MDL) Prin-  ciple for such estimation. We empirically  compared the performance of our  method based on the MDL Principle  against, the Maximum Likelihood Estimator  in word clustering, and found that  the former outperforms the latter. We  also evaluated the method by conducttug  pp-attachment disambiguation experiments  using an automatically constructed  thesaurus. Our experime. ntal  results indicate that such a thesaurus can  be used to improve accuracy in disambiguatiou.
Learning Word Association Norms Using Tree Cut Pair Models.

Learning Dependencies between Case Frame Slots
We address the problem of automatically acquiring case frame patterns (selectional patterns) from large corpus data. In particular, we propose a method of learning dependencies between case frame slots. We view the problem of learning case frame patterns as that of learning a multi-dimensional discrete joint distribution, where random variables represent case slots. We then formalize the dependencies between case slots as the probabilistic dependencies between these random variables. Since the nnmber of parameters in a multidimensional joint distribution is exponential in general, it is infiasible to accurately estimate them in practice. To overcome this difficulty, we settle with approximatiug the target joint distribution by the product of low order component distributions, based on corpus data. In particular we propose to employ an efficient learning algorithm based on the MDL principle to realize this task. Our experimental results indicate that for certain classes of verbs, the accuracy achieved in a disambiguation experiment is improved by using the acquired knowledge of dependencies.
Clustering Words with the MDL Principle
We address the problcin of automatically  constructing a thesaurus by clustertug  words based on corpus data. We view  this problem as that of estimating a joint  distribution over the Cartesian product  of a partition of a set, of nouns and a  partition of a set of verbs, and propose  a learuing algorithm based on the Minimum  Description Leugth (MDL) Prin-  ciple for such estimation. We empirically  compared the performance of our  method based on the MDL Principle  against, the Maximum Likelihood Estimator  in word clustering, and found that  the former outperforms the latter. We  also evaluated the method by conducttug  pp-attachment disambiguation experiments  using an automatically constructed  thesaurus. Our experime. ntal  results indicate that such a thesaurus can  be used to improve accuracy in disambiguatiou.
Learning Word Association Norms Using Tree Cut Pair Models

On%2Dline Learning of Binary and n%2Dary Relations over Multi%2Ddimensional Clusters.

On%2Dline Learning of Binary Lexical Relations Using Two%2Ddimensional Weighted Majority Algorithms.

Generalizing Case Frames Using a Thesaurus and the MDL Principle
this paper, we confine ourselves to the former issue, and refer the interested reader to Li and Abe (1996), which deals with the latter issue
On%2Dline Learning of Binary Lexical Relations Using Two%2Ddimensional Weighted Majority Algorithms

Generalizing Case Frames Using a Thesaurus and the MDL Principle
this paper, we confine ourselves to the former issue, and refer the interested reader to Li and Abe (1996), which deals with the latter issue

Characterizing PAC%2DLearnability of Semilinear Sets
The learnability of the class of letter-counts of regular languages (semilinear sets) and other related classes of subsets of N  d  with respect to the distribution-free learning model of Valiant (PAC-learning model) is characterized. Using the notion of reducibility among learning problems due to Pitt and Warmuth called &#034;prediction preserving reducibility,&#034; and a special case thereof, a number of positive and partially negative results are obtained. On the positive side the class of semilinear sets of dimension 1 or 2 is shown to be learnable when the integers are encoded in unary. On the neutral to negative side it is shown that when the integers are encoded in binary the learning problem for semilinear sets as well as a class of subsets of Z  d  much simpler than semilinear sets is as hard as learning DNF, a central open problem in the field. A number of hardness results for related learning problems are also given. 3  Most of the research reported herein was conducted while the aut...

Towards Realistic Theories of Learning.

Efficient Distribution%2Dfree Population Learning of Simple Concepts.

Predicting Location and Structure Of beta%2DSheet Regions Using Stochastic Tree Grammars.
We describe and demonstrate the effectiveness of a method of predicting protein secondary structures, βsheet regions in particular, using a class of stochastic tree grammars as representational language for their amino acid sequence patterns. The family of stochastic tree grammars we use, the Stochastic Ranked Node Rewriting Grammars (SRNRG), is one of the rare families of stochastic grammars that are expressive enough to capture the kind of long-distance dependencies exhibited by the sequences of β-sheet regions, and at the same time enjoy relatively efficient processing. We applied our method on real data obtained from the HSSP database and the results obtained are encouraging: Using an SRNRG trained by data of a particular protein, our method was actually able to predict the location and structure of β-sheet regions in a number of different proteins, whose sequences are less than 25 per cent homologous to the training sequences. The learning algorithm we use is an extension of the ‘Inside-Outside ’ algorithm for stochastic context free grammars, but with a number of significant modifications. First, we restricted the grammars used to be members of the ‘linear ’ subclass of SRNRG, and devised simpler and faster algorithms for this subclass. Secondly, we reduced the alphabet size (i.e. the number of amino acids) by clustering them using their physicochemical properties, gradually through the iterations of the learning algorithm. Finally, we parallelized our parsing algorithm to run on a highly parallel computer, a 32-processor CM-5, and were able to obtain a nearly linear speed-up. We emphasize that our prediction method already goes beyond what is possible by the homology-based approaches. We also stress that our method can predict the structure as well as the location of β-sheet regions, which was not possible by previous inverse protein folding methods.
Exact Learning of Linear Combinations of Monotone Terms from Function Value Queries.

The %22lob%2Dpass%22 Problem and an On%2Dline Learning Model of Rational Choice.

On the Computational Complexity of Approximating Distributions by Probabilistic Automata.
We introduce a rigorous performance criterion for training algorithms for probabilistic automata (PAs) and hidden Markov models (HMMs), used extensively for speech recognition, and analyze the complexity of the training problem as a computational problem. The PA training problem is the problem of approximating an arbitrary, unknown source distribution by distributions generated by a PA. We investigate the following question about this important, well-studied problem: Does there exist an efficient training algorithm such that the trained PAs provably converge to a model close to an optimum one with high confidence, after only a feasibly small set of training data? We model this problem in the framework of computational learning theory and analyze the sample as well as computational complexity. We show that the number of examples required for training PAs is moderate -- essentially linear in the number of transition probabilities to be trained and a low-degree polynomial in the example l...
Polynomial Learnability of Probabilistic Concepts with Respect to the Kullback%2DLeibler Divergence.

On the Sample Complexity of Various Learning Strategies in the Probabilistic PAC Learning Paradigms.

Learning Commutative Deterministic Finite State Automata in Polynomial Time.

Learning Commutative Deterministic Finite State Automata in Polynomial Time.

On the Computational Complexity of Approximating Distributions by Probabilistic Automata.
We introduce a rigorous performance criterion for training algorithms for probabilistic automata (PAs) and hidden Markov models (HMMs), used extensively for speech recognition, and analyze the complexity of the training problem as a computational problem. The PA training problem is the problem of approximating an arbitrary, unknown source distribution by distributions generated by a PA. We investigate the following question about this important, well-studied problem: Does there exist an efficient training algorithm such that the trained PAs provably converge to a model close to an optimum one with high confidence, after only a feasibly small set of training data? We model this problem in the framework of computational learning theory and analyze the sample as well as computational complexity. We show that the number of examples required for training PAs is moderate -- essentially linear in the number of transition probabilities to be trained and a low-degree polynomial in the example l...
Polynomial Learnability of Semilinear Sets.

Polynominal Learnability and Locality of Formal Grammars.

Feasible learnability of formal grammars and the theory of natural language acquisition.
l of linguistic theory, then, is [o &amp;aracterize this set of possible graalmars, hy specifiying the constraints ogen called the &#034;Universal (Irarerum&#039;&#034;. The theory of inductiw inlrence offers a precise solntion to this problem, by characl,erizing exactly what collections of (or its dual &#034;constraints on&#034;) languages satisfy the requirement for heing tle set of possible grammars, i.e. are learuable? A theory of &#034;feasibh&#039; inference is particularly interesting because the language acquisiLion process of a human inhnt is feasible, not [o mention its relevance to the techuok)gical counterpart of such a problem. In [his paper, we investigate the learuability of formal grammars for linguistic description with respect to a complexity heoretic notioa of feasible learnability called &#039;polyuomial learnability &#039;. Polynomial learnabillty was originally developed by %diant [?], [?] in the context of }earning boolean concept from examples, and subsequently generalized by Illumer ctal. for arbiCrary concep
